package leetcode.pre100;

import java.util.Arrays;

/**
 * 给定一个整数数组 nums ，找到一个具有最大和的连续子数组（子数组最少包含一个元素），
 * <p>
 * 返回其最大和。
 * <p>
 * 示例:
 * <p>
 * 输入: [-2,1,-3,4,-1,2,1,-5,4],
 * 输出: 6
 * 解释: 连续子数组 [4,-1,2,1] 的和最大，为 6。
 * <p>
 * @date 2020/3/4 17:50
 */
public class Code53_SubArrayMaxSum_最大连续子数组和 {
    /**
     * sum[i] = sum[i-1] + arr[i] ,  sum[i-1] >= 0。前i-1个和大于0，仍要累计起来
     * sum[i] = arr[i] ,    sum[i-1] < 0。前i-1个和已经小于0了，从头开始
     */
    public static int maxSubArray(int[] arr) {
        if (arr == null || arr.length == 0) return 0;
        int res = Integer.MIN_VALUE;
        int sum = 0;
        for (int i = 0; i < arr.length; i++) {
            if (sum < 0) {
                sum = arr[i];
            } else {
                //assert sum >= 0
                sum += arr[i];
            }
            res = Math.max(res, sum);
        }
        return res;
    }


}
